In the past, performance levels of microprocessor-based computer systems have increased dramatically. In particular, the operating speed of microprocessors has increased from some 100 kHz to several GHz. However, latency times for disk drive accesses have barely improved over the past few years, especially when compared to other speed improvements in the storage and computing fields. As a result, users are often deprived of the full benefit of the increased performance by the microprocessors. For example, when an application is started up, the large majority of time is often spent on loading data needed by an application into the memory from the disk drive. This means that the performance experienced by the user is often dominated by parameters of the storage system, not by the microprocessor. The user then often does not see any difference in performance whether his is using a system equipped with e.g. a 500 MHz microprocessor or a 1 GHz microprocessor. Therefore, the invention aims at improving latency times for storage media in general, and disk drives in particular, for selected, common or time-critical read accesses.
In the prior art U.S. Pat. No. 5,802,593, a method and apparatus for improving disk drive performance is described. The apparatus is programmed with a plurality of programming instructions for generating, if possible, an alternative disk block allocation for a current disk block allocation that will yield improved overall access time for a sequence of disk accesses. In some embodiments, the programming instructions include a logic for tracing a sequence of disk accesses to determine the current disk block allocation, a logic for generating the alternative disk block allocation, if possible, using the trace results, and a logic for effectuating the alternate disk block allocation, if generated. In one particular embodiment, the logic for generating the alternative disk block allocation employs a random search approach, while in another embodiment; the logic for generating the alternative disk block allocation employs a heuristic approach.
In the U.S. Pat. No. 5,890,205 an optimized application installation using disk block relocation is described. A computer system is programmed with a plurality of programming instructions for implementing a software function, having an installation utility with logic for generating, if possible, an alternative disk block allocation for a current disk block allocation that will yield improved overall access time for a sequence of disk accesses. In some embodiments, the logic includes logic for tracing a sequence of disk accesses to determine the current disk block allocation, logic for generating the alternative disk block allocation, if possible, using the trace results, and logic for effectuating the alternate disk block allocation, if generated. In one particular embodiment, the logic for generating the alternative disk block allocation employs a random search approach, while in another embodiment; the logic for generating the alternative disk block allocation employs a heuristic approach.
In the U.S. Pat. No. 5,920,896 an apparatus for reducing operating system start-up/boot time through disk block reallocation is described. Therefore, a computer system is equipped with an operating system having a tracer driver for generating trace data including disk locations accessed for disk accesses made by various components of the operating system during system startup/boot time. The tracer driver is loaded at an initial phase of system start-up. The computer system is further equipped with a companion disk block relocation driver for generating, if possible, an alternative disk block allocation for a current disk block allocation that will yield improved overall access time for a sequence of disk accesses. In some embodiments, the disk block relocation driver includes logic for tracing the sequence of disk accesses to determine the current disk block allocation, logic for generating the alternative disk block allocation, if possible, using the trace results, and logic for effectuating the alternate disk block allocation, if generated. In one particular embodiment, the logic for generating the alternative disk block allocation employs a random search approach, while in another embodiment; the logic for generating the alternative disk block allocation employs a heuristic approach.
Finally, in the document U.S. Pat. No. 6,317,875 B1 a method and apparatus for improving execution time performance through disk block relocation is depicted. The execution time performance of one or more applications that are dynamically loaded for execution post initial loading is improved by invoking selected parts of the one or more applications for execution post initial loading to allow disk locations accessed and the order the disk locations are accessed to load the selected parts of the one or more applications for execution post initial loading to be traced, and in turn, based at least in part on the order the disk locations are accessed, alternate disk locations to be identified to store the selected parts of the one or more applications to reduce time required to load the selected parts of the one or more applications for execution post initial loading.
The embodiments explained in the above mentioned patents are all based on the same basic idea: the program execution is traced and then the blocks are reallocated, i.e. moved from one place to another, to improve the access time. The embodiments differ in the actual mechanisms used and applications targeted, but all rely on the same principle mentioned.
In “Improving Disk Performance Via Latency Reduction”, Spencer W., IEEE Transactions On Computers, Vol. 40, No. 1, January 1991, it is proposed to provide a second disk comprising a copy of data in order to improve access time. So does “Trading Capacity for Performance in a Disk Array”, Xiang Yu et al., Proceedings Fourth Symposium on Operating Systems Design and Implementation, October 2000.
In “Adaptive Block Rearrangement”, Sedat Akyuerek and Kenneth Salem, Proceedings of the Ninth International Conference on Data Engineering, Apr. 19-23, 1993, Vienna, Austria, data blocks are copied from their original locations to preserved space near the middle of the disk. Seek times should be cut.
The approach in the prior art is mainly targeted at single-threaded/single-process operations, where the sequence of events does not change and a single data block is mostly used as part of a single sequence. When multiple threads of execution exist, e.g. multiple operations are commonly started in parallel, such as the system start-up in a multitasking environment or a user login/multiple application starts, the approach in the prior art may not be efficient, as the improved (and thus changed) timing of disk accesses could lead to a different execution order and thus a different block request order. Therefore, it is necessary in this context to generously prefetch data sequentially, in order to avoid more seek operations. Also, an iterative retracing may be required to adapt to the changing request order as a result of block rearrangement.